//
// Created by 高森森 on 2022/2/11.
//

#ifndef LEETCODE_SOLUTION36_H
#define LEETCODE_SOLUTION36_H
#include<iostream>
#include<vector>
#include<queue>
#include <algorithm>
using namespace std;

class Solution36 {
public:
    int res=0;
    vector<vector<int>>dp;
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        vector<vector<int>>graph(colors.size());
        for(auto edge:edges){
            graph[edge[0]].emplace_back(edge[1]);
        }
        dp=vector<vector<int>>(colors.size(),vector<int>(26,0));
        vector<int>visited(colors.size(),0);
        for(int i=0;i<colors.size();i++)
        {
            if(!dfs(i,visited,colors,graph))
                return -1;
        }
        return res;
    }
    bool dfs(int u,vector<int>&visited,string &color,vector<vector<int>>&graph){
        if(visited[u]==-1)
            return true;
        if(visited[u]==1)
            return false;
        visited[u]=1;
        for(auto neigh:graph[u]){
               if(!dfs(neigh,visited,color,graph))
                   return false;
            for(int k=0;k<26;k++)
                dp[u][k]=max(dp[u][k],dp[neigh][k]);

        }
        visited[u]=-1;
        dp[u][color[u]-'a']++;
        res=max(res,dp[u][color[u]-'a']);
        return true;
    }
    int largestPathValue2(string colors, vector<vector<int>>& edges) {
        vector<vector<int>>graph(colors.size());
        vector<int>indeg(colors.size());//拓扑排序记录入度
        for(auto edge:edges){
            indeg[edge[1]]++;
            graph[edge[0]].emplace_back(edge[1]);
        }
        vector<vector<int>>f(colors.size(),vector<int>(26,0));
        int found=0;
        queue<int>que;
        for(int i=0;i<colors.size();i++)
        {
            if(indeg[i]==0){
                que.push(i);
            }
        }
        while(!que.empty()){
            found++;
            int node=que.front();
            que.pop();
            f[node][colors[node]-'a']++;
            for(int neigh:graph[node]){
                indeg[neigh]--;
                //状态转换方程
                for(int i=0;i<26;i++)
                {
                    f[neigh][i]=max(f[neigh][i],f[node][i]);
                }
                if(indeg[neigh]==0)
                    que.push(neigh);
            }
        }
        if(found!=colors.size())
            return -1;
        for(int i=0;i<colors.size();i++)
            res=max(res,*max_element(f[i].begin(),f[i].end()));
        return res;
    }
};


#endif //LEETCODE_SOLUTION36_H
